package leetcode;


public class Code04_1 {

    public static void main(String[] args) {
        System.out.println(new Code04_1().findMedianSortedArrays(
                new int[]{3},
                new int[]{1,2}
        ));
    }

    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int all = nums1.length + nums2.length;
        if ((all) % 2 == 0) {
            return (finditme(nums1, nums2, all / 2) + finditme(nums1, nums2, all / 2 + 1)) / 2.0;
        } else {
            return (double) finditme(nums1, nums2, all / 2 + 1);
        }

    }

    public int finditme(int[] n1, int[] n2, int k) {
        if (n1.length > n2.length) {
            return finditme(n2, n1, k);
        }
        int n1index = n1.length < k ? n1.length : k;
        int n2index = k - n1index;
        while (true) {
            int n1l = n1index == 0 ? Integer.MIN_VALUE : n1[n1index - 1];
            int n1r = n1index == n1.length ? Integer.MAX_VALUE : n1[n1index];
            int n2l = n2index == 0 ? Integer.MIN_VALUE : n2[n2index - 1];
            int n2r = n2index == n2.length ? Integer.MAX_VALUE : n2[n2index];
            if (n1l > n2r) {
                int n = n2index/2==0?1:n2index/2;
                int end1 = n1index-n<0?n1index:n;
                int end2 = n2index+n>n2.length?n2.length-n2index:n;
                end1 = Math.min(end1,end2);
                n1index-=end1;
                n2index+=end1;
            } else if (n2l > n1r) {
                int n = n1index/2==0?1:n1index/2;
                int end1 = n2index-n<0?n2index:n;
                int end2 = n1index+n>n1.length?n1.length-n1index:n;
                end1 = Math.min(end1,end2);
                n2index-=end1;
                n1index+=end1;
            } else {
                return Math.max(n1l, n2l);
            }
        }
    }


    public double findMedianSortedArrays2(int[] nums1, int[] nums2) {
        int len1 = nums1.length;
        int len2 = nums2.length;
        int size = len1 + len2;
        if (size % 2 == 1) {
            return findKth(nums1, 0, len1, nums2, 0, len2, size / 2 + 1);
        } else {
            final double r1 = findKth(nums1, 0, len1, nums2, 0, len2, size / 2);
            final double r2 = findKth(nums1, 0, len1, nums2, 0, len2, size / 2 + 1);
            return (r1 + r2) / 2;
        }
    }

    public double findKth(int[] nums1, int start1, int len1,
                          int[] nums2, int start2, int len2,
                          int k) {
        //短的数组放前面
        if (len1 - start1 > len2 - start2) {
            return findKth(nums2, start2, len2, nums1, start1, len1, k);
        }
        if (len1 - start1 == 0) {
            return nums2[k - 1];
        }
        if (k == 1) {
            return Math.min(nums1[start1], nums2[start2]);
        }
        int p1 = start1 + Math.min(len1 - start1, k / 2);
        int p2 = start2 + k - p1 + start1;
        if (nums1[p1 - 1] < nums2[p2 - 1]) {
            return findKth(nums1, p1, len1, nums2, start2, len2, k - p1 + start1);
        } else if (nums1[p1 - 1] > nums2[p2 - 1]) {
            return findKth(nums1, start1, len1, nums2, p2, len2, k - p2 + start2);
        } else {
            return nums1[p1 - 1];
        }
    }
}
